package subjectlist;

public class I如何求数组中连续最大和 {


    private static class 动态规划{

        public static void main(String[] args) {
            int arr[]={1,2,3,4,5,1,2,3,5,12,12,55,22,55};
            System.out.println(maxSubArray(arr));
        }
        public static int maxSubArray(int[] arr){
            if (arr == null || arr.length < 1) {
                System.out.println("参数不合理");
                return -1;
            }
            int n=arr.length;
            int[]end=new int[n];//初始化数组大小
            int[]all=new int[n];//初始化数组大小
            end[n-1]=arr[n-1];//初始化数组中最后一个元素
            all[n-1]=arr[n-1];//初始化数组中最后一个元素
            end[0]=all[0]=arr[0];//初始化数组第一个元素
            for (int i = 1; i < n; ++i) {
                end[i]=Integer.max(end[i-1]+arr[i],arr[i]);
                all[i]=Integer.max(end[i],all[i-1]);
            }
            return all[n-1];
        }
    }

    private static class 优化动态规划{

        public static void main(String[] args) {
            System.out.println(true & true);
        }
        public static int maxSubArray(int[] arr){
            if (arr == null || arr.length < 1) {
                System.out.println("参数不合理");
                return -1;
            }
            int all=arr[0];//最大子数组和
            int end=arr[0];//包含最后一个元素的最大子数组和
            for (int i = 1; i < arr.length; ++i) {
                //相邻两个相加跟后一个元素对比取最大的
                end=Integer.max(end+arr[i],arr[i]);
                //跟之前的累加的比较
                all=Integer.max(end,all);
            }
            return all;
        }
    }
}
